Bipartite Matching

释义 Definition

二分图匹配：在一个二分图（顶点可分为两组，且边只连接不同组的顶点）中，选取一组边，使得任意两个被选中的边不共享端点。常见目标是求最大二分图匹配（匹配边数最多）。

发音 Pronunciation (IPA)

/baɪˈpɑːrtaɪt ˈmætʃɪŋ/

例句 Examples

We used bipartite matching to assign students to projects.
我们用二分图匹配把学生分配到项目中。

In the scheduling system, maximum bipartite matching ensures that the largest possible number of tasks are paired with available workers without conflicts.
在排班系统中，最大二分图匹配可以在不冲突的前提下，让尽可能多的任务与可用工人配对。

词源 Etymology

bipartite 来自拉丁语前缀 *bi-*（“二、两”）+ part（“部分”相关词根），字面意思是“分成两部分的”。matching 源于 “match”（配对、匹配）。合起来表示“在两部分（两侧）之间进行配对的匹配问题”，对应图论中的二分图结构。

相关词 Related Words

• Augmenting Path
• Bipartite Graph
• Flow Network
• Hall's Theorem
• Hopcroft–Karp Algorithm
• Matching
• Maximum Matching
• Minimum Vertex Cover

文学与经典著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在图算法章节讨论匹配、增广路思想，并常提及二分图匹配及其与网络流的联系。
• Algorithm Design（Kleinberg & Tardos）：用二分图匹配建模分配/指派问题，介绍求解思路与应用。
• The Algorithm Design Manual（Steven S. Skiena）：把二分图匹配作为常用“可套用”的经典问题模板之一。
• Combinatorial Optimization: Polyhedra and Efficiency（Alexander Schrijver）：在组合优化框架下系统讨论匹配理论（含二分图匹配）。
• Graph Theory（Reinhard Diestel）：在图论基础内容中涉及匹配及相关定理与概念。